5.0 KB · ⇊ 2 parts · ⤓ Micron 5.0 KB · ⤓ HTML 27.5 KB

top

Nella mwbqteoria della complessità computazionale, la classe di problemi mwbgPSPACE, che sta per mwbwpolynomial space, è l'insieme di tutti i problemi che possono essere risolti da una mwcamacchina di Turing deterministica usando una quantità di memoria di mwcq O ( n k ) {\displaystyle O(n^{k})} , dove mwcg n {\displaystyle n} è la dimensione dei dati di input e mwcw k {\displaystyle k} è un qualsiasi valore finito.

In altre parole, PSPACE include quei problemi che possono essere risolti da un mwdqalgoritmo che utilizzi uno spazio di memoria la cui dimensione sia al più mwdgfunzione mwdwpolinomiale della dimensione dell'input.

Per il mwegteorema di Savitch, questa classe risulta equivalente a NPSPACE, cioè la classe di problemi che possono essere risolti da una macchina di Turing non deterministica usando una quantità di memoria di mwfa O ( n k ) {\displaystyle O(n^{k})} . Ciò significa che le due classi sono equivalenti in termini di potenza computazionale. Inoltre si osserva facilmente che la ben più conosciuta classe di complessità mwfqP è inclusa in PSPACE. Infatti, è evidente che se un algoritmo ha un tempo di esecuzione mwfg t {\displaystyle t} , potrà utilizzare al più mwfw t {\displaystyle t} celle di memoria; se quindi sappiamo che mwga t = O ( n k ) {\displaystyle t=O(n^{k})} per un qualche mwgq k {\displaystyle k} , necessariamente lo spazio utilizzato è limitato allo stesso modo.

Questo stesso ragionamento, unito all'osservazione fatta prima che PSPACE = NPSPACE, ci permette di dimostrare anche l'inclusione mwgwNP mwha ⊂ ⊂ {\displaystyle \subset } PSPACE. L'inclusione opposta invece non è dimostrata, e anzi è opinione comune che sia falsa, ovvero che PSPACEmwhq ⊄ {\displaystyle \not \subset } NP. Questo implicherebbe quindi PSPACEmwhg ⊄ {\displaystyle \not \subset } P.

Ad accreditare in particolare questa ultima congettura si aggiunge l'esistenza di problemi mwiaNP completi appartenenti alla classe PSPACE. Ad esempio, è possibile risolvere in tempo esponenziale ma con utilizzo di memoria polinomiale il mwiqproblema del commesso viaggiatore: date mwig n {\displaystyle n} città, è sufficiente mwiwcontare in base mwja n {\displaystyle n} i percorsi possibili, che saranno quelli associati ai numeri di mwjq n {\displaystyle n} cifre tutte distinte (questo conteggio richiede una quantità di memoria mwjglineare nel numero di città) e per ogni percorso calcolare la somma delle distanze tra le varie città (anche questa operazione ha costo lineare in spazio). Questo significa che se fosse vero che PSPACE mwjw ⊂ ⊂ {\displaystyle \subset } P, sarebbe anche vero NP-C mwka ⊂ ⊂ {\displaystyle \subset } P, e quindi NP mwkq ⊂ ⊂ {\displaystyle \subset } P (ossia tutti i problemi decidibili in tempo polinomiale rispetto alla dimensione dell'input da una macchina di Turing non deterministica sarebbero decidibili in tempo polinomiale anche da una macchina di Turing deterministica). Dato che le macchine di Turing deterministiche sono un caso particolare di macchine non deterministiche ne risulta che P mwkg ⊂ ⊂ {\displaystyle \subset } NP, e quindi P = NP. La domanda "P=NP o P mwkw ≠ ≠ {\displaystyle \neq } NP?" è uno dei mwlaproblemi del millennio, ad oggi non risolto, anche se molti esperti credono che P mwlq ≠ ≠ {\displaystyle \neq } NP.